#pragma once
#include <iostream>
#include <vector>
using namespace std;

template <class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;  //转成数字，把key
	}
};


// 特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};



//namespace open_address
//{
//	enum State
//	{
//		EXIST, // 0 该值存在的标记
//		EMPTY, // 1 初始化的标记
//		DELETE // 2  删去之后的标记
//	};
//
//	template <class K, class  V>
//	struct HashData
//	{
//		pair<K, V> _kv;
//		State _state = EMPTY; //状态表示的标记
//	};
//
//	template <class K, class V, class Hash = HashFunc<K>>
//	class HashTable
//	{
//	public:
//		HashTable()
//		{
//			_tables.resize(10);
//		}
//
//		bool Insert(const pair<K, V>& kv)
//		{
//			if (Find(kv.first)) return false; //防止数据冗余
//			//扩容
//			if (_n * 10 / _tables.size() >= 7)
//			{
//				////_tables.resize(_tables.size() * 2);
//				//vector<HashData<K, V>> newTables(_tables.size() * 2);
//				////遍历旧表，将所有数据映射到新表
//				//_tables.swap(newTables); //该方法不好，当冲突的时候，用+1的方法时，得重写下面构造
//
//				//遍历创建新影身，复用Insert
//				// 此处只需将有效元素搬移到新哈希表中
//				// 已删除的元素不用处理
//				HashTable<K, V, Hash>newHT;
//				newHT._tables.resize(_tables.size() * 2);
//				for (size_t i = 0; i < _tables.size(); i++) {
//					if (_tables[i]._state == EXIST) newHT.Insert(_tables[i]._kv);
//				}
//				_tables.swap(newHT._tables);
//			}
//
//			Hash hs;
//			size_t hashi = hs(kv.first) % _tables.size();
//			while (_tables[hashi]._state == EXIST) { //若存在，则表示出现了哈希冲突
//				++hashi;
//				hashi %= _tables.size();
//			}
//			_tables[hashi]._kv = kv;
//			_tables[hashi]._state = EXIST;
//			++_n;
//
//			return true;
//		}
//
//		HashData<K, V>* Find(const K& key)
//		{
//			Hash hs;
//			size_t hashi = hs(key) % _tables.size(); //算在表里的位置
//			while (_tables[hashi]._state != EMPTY) 
//			{ //之所以用不等于ENPTY，而不是EXIST，是因为避免查找的数出现过哈希冲突之后，位置移动，然后前面的数被删，比如：
//			  // 11(EXIST) 21（DELETE）31（key） 41(EXIST)
//				if (_tables[hashi]._state == EXIST &&
//					_tables[hashi]._kv.first == key) {
//					return &_tables[hashi];
//				}
//				
//				++hashi;
//				hashi %= _tables.size(); //防止越界
//			}
//			return nullptr;
//		}
//
//		bool Erase(const K& key)
//		{
//			HashData<K, V>* ret = Find(key);
//			if (ret == nullptr) return false;
//			else {
//				ret->_state = DELETE;
//				return true;
//			}
//		}
//
//	private:
//		vector<HashData<K, V>> _tables; //不用构建析构，因为vector本身就有析构
//		size_t _n;
//	};
//
//
//	void TestHT1()
//	{
//		HashTable<int, int> ht;
//		int a[] = { 11,21,4,14,24,15,9 };
//		for (auto e : a)
//		{
//			ht.Insert({ e,e });
//		}
//		ht.Insert({ 19, 19 });
//		ht.Insert({ 19,190 });
//
//		cout << ht.Find(24) << endl;
//		ht.Erase(4);
//		cout << ht.Find(24) << endl;
//		cout << ht.Find(4) << endl;
//
//		ht.Insert({ 4,4 });
//	}
//
//	struct StringHashFunc
//	{
//		size_t operator()(const string& s)
//		{
//			size_t hash = 0;
//			for (auto e : s)
//			{
//				hash *= 31;
//				hash += e;
//			}
//			return hash;
//		}
//	};
//
//	void TestHT2()
//	{
//		//HashTable<string, string, StringHashFunc> ht; //但是注释第三个，则会出现“类型强制转换” : 无法从“const K”转换为“size_t”
//		HashTable<string, string> ht; //使用特化，就可以支持该操作
//
//
//
//		ht.Insert({ "sort", "排序" });
//		ht.Insert({ "left", "左边" });
//
//		//string s1("sort");
//		//string s2("sort");
//
//		cout << StringHashFunc()("bacd") << endl;
//		cout << StringHashFunc()("abcd") << endl;
//		cout << StringHashFunc()("aadd") << endl;
//	}
//}






//——————————步骤——————————

// 1、实现哈希表
// 2、封装unordered_map和unordered_set 解决KetOfT
// 3、iterator
// 4、const_iterator
// 5、修改Key的问题
// 6、解决operate[]


namespace hash_bucket  //哈希桶-链式
{
	template<class T> //用一个值来确定底层存的是什么
	struct HashNode
	{
		/*pair<K, V> _kv;
		HashNode<K, V>* _next;*/

		T _data;
		HashNode<T>* _next;

		HashNode(const T&data)
			: _data(data)
			, _next(nullptr)
		{}
	};

	//前置声明
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	//template<class K, class T, class KeyOfT, class Hash>
	template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash> 
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;

		Node* _node;
		const HashTable<K, T, KeyOfT, Hash>* _pht; //由于向上找不到，老是会报_pht找不到，因此我们需要加个前置声明

		HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht) //需要用const版本，防止权限放大
			:_node(node)
			,_pht(pht)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}


		Self& operator++()
		{
			if (_node->_next) //当前桶还有节点
			{ 
				_node = _node->_next;
			}
			else //当前桶遍历完毕，找下一个不为空的桶
			{
				KeyOfT kot;
				Hash hs;
				size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
				
				++hashi;
				while (hashi < _pht->_tables.size()) //由于pht要访问其成员私有，但是无法访问，我们解决方法就是提法gettable或者提供友元
				{
					if (_pht->_tables[hashi]) 
						break; //找到不为空的桶 
					++hashi;
				}
				if (hashi == _pht->_tables.size()) //说明已经走完
				{
					_node = nullptr;
				}
				else _node = _pht->_tables[hashi];
			}
			return *this;
		}


	};

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		//友元声明
		template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash> //普通类的友元直接友元声明即可，而类模板需要把模板参数带上
		friend struct HTIterator;

		typedef HashNode<T> Node;
	
	public:
		typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;  //迭代器
		typedef HTIterator<K, T, const T*,const T&, KeyOfT, Hash> ConstIterator; //const迭代器


		Iterator Begin()
		{
			if (_n == 0) return End(); //如果没有数据
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return Iterator(cur, this);
				}
			}
			return End();
		}

		Iterator End()
		{
			return Iterator(nullptr, this);
		}


		ConstIterator Begin() const
		{
			if (_n == 0) return End(); //如果没有数据
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return ConstIterator(cur, this);
				}
			}
			return End();
		}

		ConstIterator End()const
		{
			return ConstIterator(nullptr, this); 
		}

	public:
		HashTable()
		{
			_tables.resize(10, nullptr);
		}

		~HashTable()
		{ // 依次把每个桶释放
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}


		pair<Iterator, bool> Insert(const T& data) //使用的是头插
		{
			KeyOfT kot;
			Iterator it = Find(kot(data));
			//去重
			if (it != End()) //return false;
				return make_pair(it, false);
				
			Hash hs;
			size_t hashi = hs(kot(data)) % _tables.size();
			//负载因子 == 1扩容，
			// 越低，空间效率越低，时间效率越高
			///越高，空间效率越高，时间效率越低
			if (_n == _tables.size())
			{

				vector<Node*> newtables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur) 
					{ 
						Node* next = cur->_next;
						//旧表中节点，挪动新表重新映射的位置
						size_t hashi = hs(kot(cur->_data)) % newtables.size();
						//头插到新表
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);

			}

			//头插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return make_pair(Iterator(newnode, this),true);
		}

		Iterator Find(const K& key)
		{
			KeyOfT kot;

			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key) return Iterator(cur, this);
				cur = cur->_next;
			}
			return End();
		}

		bool Erase(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr) //如果是第一个节点 
					{
						_tables[hashi] = cur->_next;
					}
					else //否则，则让前一个指向我的后一个
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;
					return true;
				}

				prev = cur;  
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<Node*> _tables; //指针数组，数组的每个位置存的是指针
		size_t _n; //表中存储数据个数
	};

}